﻿// 0725evalRPN.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include <sstream>
#include <string>
#include <vector>
#include <stack>
using namespace std;


/*
根据 逆波兰表示法，求表达式的值。
有效的算符包括 +、-、*、/ 。每个运算对象可以是整数，也可以是另一个逆波兰表达式。
注意 两个整数之间的除法只保留整数部分，向零截断。
可以保证给定的逆波兰表达式总是有效的。换句话说，表达式总会得出有效数值且不存在除数为 0 的情况。

输入：tokens = ["2","1","+","3","*"]
输出：9
解释：该算式转化为常见的中缀算术表达式为：((2 + 1) * 3) = 9

输入：tokens = ["4","13","5","/","+"]
输出：6
解释：该算式转化为常见的中缀算术表达式为：(4 + (13 / 5)) = 6
 */

/*
 输入：s = "1 + 1"
 输出：2

 输入：s = " 2-1 + 2 "
 输出：3

 输入：s = "(1+(4+5+2)-3)+(6+8)"
 输出：23

 */

class Solution
{
public:
	int calculate(string s)
	{
		string oh_str = s;
		int str_size = oh_str.size();
		stack<long>oh_stack;

		long result = 0;
		int sign = 1;
		for (int i=0; i<str_size;i++)
		{
			char oh_char = oh_str[i];
			if (oh_char>='0' && oh_char<='9')
			{
				long curr_val = oh_char - '0'; //char转int
				while (i+1<str_size && oh_str[i+1]>='0' && oh_str[i+1]<='9')
				{
					int next_val = oh_str[i + 1] - '0';
					curr_val = curr_val * 10 + next_val;
					i++;
				}
				//2-1+2
				result = result + (sign * curr_val);
				//cout << sign * curr_val;
			}
			else if (oh_char == '+')
			{
				sign = 1;
			}
			else if (oh_char == '-')
			{
				sign = -1;
			}
			else if (oh_char=='(')
			{
				//左边的数字压栈
				oh_stack.push(result);

				//左边的符号压栈
				oh_stack.push(sign);

				result = 0;
				sign = 1;

			}
			else if (oh_char==')')
			{
				int pre_sign = oh_stack.top();
				oh_stack.pop();

				long prev_result = oh_stack.top();
				oh_stack.pop();

				result = prev_result + pre_sign * result;
			}
		}
		return result;
	}
	int evalPRN(vector<string>&tokens)
	{
		stack<long int>result;
		long int answer;
		for (auto & token_item :tokens)
		{
			if (token_item == "+")
			{
				
				long int right_num = result.top();
				result.pop();

				long int left_num = result.top();
				result.pop();

				answer = left_num + right_num;
			}
			else if (token_item == "-")
			{
				long int right_num = result.top();
				result.pop();

				long int left_num = result.top();
				result.pop();

				answer = left_num - right_num;
			}
			else if (token_item == "*")
			{
				long int right_num = result.top();
				result.pop();

				long int left_num = result.top();
				result.pop();

				answer = left_num * right_num;
			}
			else if (token_item == "/")
			{
				long int right_num = result.top();
				result.pop();

				long int left_num = result.top();
				result.pop();

				answer = left_num / right_num;
			}
			else
			{
				answer = stoi(token_item);
			}

			result.push(answer);
		}
		return result.top();
	}
};


/*
设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。
- push(x) —— 将元素 x 推入栈中。
- pop() —— 删除栈顶的元素。
- top() —— 获取栈顶元素。
- getMin() —— 检索栈中的最小元素。
 */

class MinStack {
public:
	stack<int>oh_stack;
	stack<int>min_stack;

	MinStack() {

	}

	void push(int val) {
		oh_stack.push(val);
		if (!min_stack.empty())
		{
			int min_top = min_stack.top();
			min_stack.push(min(min_top, val));
		}
		else
		{
			min_stack.push(val);
		}
		
	}

	void pop() {
		oh_stack.pop();
		min_stack.pop();
	}

	int top() {
		return oh_stack.top();
	}

	int getMin() {
		return min_stack.top();
	}
};

int main()
{
	{
		/*
		 * ["MinStack","push","push","push","getMin","pop","top","getMin"]
			[[],[-2],[0],[-3],[],[],[],[]]
		 */

		MinStack min_stack;
		min_stack.push(-2);
		min_stack.push(0);
		min_stack.push(-3);
		min_stack.getMin();

		return 0;
	}

	vector<string> tokens = { "4","13","5","/","+" };
	Solution solution;
	//cout << solution.evalPRN(tokens);

	cout << solution.calculate("(1+(4+5+2)-3)+(6+8)");
}

// 运行程序: Ctrl + F5 或调试 >“开始执行(不调试)”菜单
// 调试程序: F5 或调试 >“开始调试”菜单

// 入门使用技巧: 
//   1. 使用解决方案资源管理器窗口添加/管理文件
//   2. 使用团队资源管理器窗口连接到源代码管理
//   3. 使用输出窗口查看生成输出和其他消息
//   4. 使用错误列表窗口查看错误
//   5. 转到“项目”>“添加新项”以创建新的代码文件，或转到“项目”>“添加现有项”以将现有代码文件添加到项目
//   6. 将来，若要再次打开此项目，请转到“文件”>“打开”>“项目”并选择 .sln 文件
